Programmers, whether writing for general purpose computers or specific data processors such as digital signal processors, DSP, choose to write in a high level programming language, such as C, because it is easily readable by a human and because the computer program may be automatically recompiled for different processors making it easier to reuse. These high level programs need to be translated into computer executable code. Typically this is done by a compiler in a multi phase process. In a first phase the high level language is processed to form a platform independent intermediate representation of the program. The platform independent representation might make explicit machine level constructs such as address calculation and the loading and storing values from memory, but the operations represented are generic and are available in the instruction set of all target processors. A second phase of processing takes these generic operations and converts them into platform specific machine instructions.
In practice all compilers can be divided into a part that is concerned with the source language often called the “front end” and a part that generates code and needs to know about the machine—the “back end” or “code generator”. The two parts often communicate via a generic intermediate representation which is the representative form used herein. In many compilers the front-end runs for a period converting a piece of the high level program to intermediate representation then the back-end is called to generate machine instructions for that piece of the high level program, then the front-end runs again for the next piece of the high level program and so on.
An important part of the work performed in the code generator is “instruction selection” which chooses sequences of machine instructions to represent each generic operation in the intermediate representation. A simple approach is to replace each occurrence of a generic operation with a corresponding sequence of machine instructions in a one to one relationship. More sophisticated compilers seek to choose instructions according to the context of the generic operation within the intermediate representation depending on the operations surrounding or associated with that specific operation. Such a technique is implemented in compilers which perform “tree pattern matching”. However, tree pattern matching has some limitations. More specifically it only works on tree like data structures and is limited to processing expressions in isolation. A closely related technique is directed acyclic graph, DAG, pattern matching. However, both of these techniques are limited to “straight line code” that is specifically they do not cope with code that contains loops.
The inability to handle loops is a significant drawback of tree pattern matching as the relationship of a generic operation to operations in previous and future iterations of the loop cannot influence the choice of machine instructions used to replace it. However it does not prevent the use of tree or DAG pattern matching to select instructions for the straight-line section of code within the loop.
Compilers have been the subject of much study since a poor compilation affects processor performance during task execution. Many techniques have been proposed to “optimise” compiler performance although in general such techniques result in executable code which is improved rather than optimised. Some of these require (or are much improved by) the transformation of the source code into a “single static assignment” form where every variable is only assigned once. Consider, for example, the code:Y=1Y=4X=Y
We can easily see that the first assignment is redundant and that the value in the third line of code comes from the second line of code. A compiler would have to perform a definition analysis to determine this, and such an analysis would be computationally expensive.
If however the same code was transformed into a single static assignment form, then we would have:Y1=1Y2=4X1=Y2 
This representation of the source code makes it much easier to apply optimisation techniques such as sparse conditional constant propagation, global value numbering and dead code elimination.